home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / appletalk / uab.shar / hash.h < prev    next >
C/C++ Source or Header  |  1990-07-12  |  5KB  |  128 lines
  1. /*
  2.  * $Author: cck $ $Date: 88/09/14 10:19:40 $
  3.  * $Header: /src/local/mac/cap/etalk/RCS/hash.h,v 1.11 88/09/14 10:19:40 cck Rel $
  4.  * $Revision: 1.11 $
  5. */
  6.  
  7. /*
  8.  * hash.h - external definitions for hash.c - generalized hashing function
  9.  *
  10.  *  written by Charlie C. Kim
  11.  *     Academic Networking, Communications and Systems Group
  12.  *     Center For Computing Activities
  13.  *     Columbia University
  14.  *   September 1988
  15.  *
  16.  *
  17.  * Copyright (c) 1988 by The Trustees of Columbia University 
  18.  *  in the City of New York.
  19.  *
  20.  * Permission is granted to any individual or institution to use,
  21.  * copy, or redistribute this software so long as it is not sold for
  22.  * profit, provided that this notice and the original copyright
  23.  * notices are retained.  Columbia University nor the author make no
  24.  * representations about the suitability of this software for any
  25.  * purpose.  It is provided "as is" without express or implied
  26.  * warranty.
  27.  *
  28.  *
  29.  * Edit History:
  30.  *
  31.  *  Sept 5, 1988  CCKim Created
  32.  *  Sept 6, 1988  CCKim Finished: level 0
  33.  *
  34. */
  35.  
  36. #ifndef _HASH_HEADER_INCLUDED
  37. #define _HASH_HEADER_INCLUDED "yes"
  38.  
  39. /* hash table operations recognized */
  40. #define HASH_OP_DELETE 2
  41. #define HASH_OP_MEMBER 1 
  42. #define HASH_OP_INSERT 0
  43. #define HASH_OP_NUM 3
  44.  
  45. #define HASH_OP_VALID(n) ((n) < HASH_OP_NUM && (n) >= HASH_OP_INSERT)
  46. #define HASH_OP_INVALID(n) ((n) >= HASH_OP_NUM || (n) < HASH_OP_INSERT)
  47.  
  48. /* hashing collision policies */
  49. #define HASH_POLICY_OLD -1    /* old for redefine */
  50. #define HASH_POLICY_CHAIN 0    /* chain on collisions */
  51. #define HASH_POLICY_LINEAR_PROBE 1 /* linear probes on collisions */
  52. #define HASH_POLICY_DOUBLE_HASH 2 /* double hash on collisions */
  53.  
  54. /* given a hash policy, returns true if it is a valid policy */
  55. #define HASH_POLICY_VALID(n) ((n) <= HASH_POLICY_DOUBLE_HASH && \
  56.                   (n) >= HASH_POLICY_CHAIN)
  57. #define HASH_POLICY_LINKSNEEDED(n) ((n) == HASH_POLICY_CHAIN)
  58.  
  59. /* hash function types */
  60. #define HASH_TYPE_OLD -1    /* old for redefine */
  61. #define HASH_TYPE_OWN 0        /* our own */
  62. #define HASH_TYPE_DIVISION 1    /* division method */
  63. #define HASH_TYPE_MULTIPLICATIVE 2 /* multiplicative method */
  64. /* for multiplicative mode: try for fibonacci */
  65. /* only valid for 32 bit machines! */
  66. #define A_MULTIPLIER 2630561063 /* gotta figure out a good one */
  67.  
  68. #define HASH_TYPE_NUM 3
  69.  
  70. #define HASH_TYPE_VALID(n) ((n) < HASH_TYPE_NUM && \
  71.   (n) >= HASH_TYPE_OWN)
  72.  
  73.  
  74. /*
  75.  * structure to allow operations other than a linear list off a hash
  76.  * bucket in the chain policy
  77.  *
  78. */
  79. struct hash_bucket_list_ops {
  80.   caddr_t (*hlo_find)();    /* find a member */
  81.   caddr_t (*hlo_insert)();    /* insert a member (returns ptr to */
  82.                 /* data) */
  83.   int (*hlo_delete)();        /* delete a member */
  84.   caddr_t (*hlo_get)();        /* get any member and remove from list */
  85. };
  86.  
  87. /* averages are fixed decimal with 2 digits after the decimal */
  88. /* they are kept in case we want to do something when average */
  89. /* distances get too large */
  90. struct hash_statistics {
  91.   int hs_buckets;        /* number of buckets in table */
  92.   /* describes # of entries in chain */
  93.   int hs_used;            /* # of buckets filled */
  94.   /* describes table (not accurate for chain policy) */
  95.   int hs_davg;            /* average distance from hash index */
  96.   int hs_dsum;            /* sum of distances from hash index */
  97.   int hs_dmax;            /* maximum distance from hash index */
  98.   /* describes lookup patterns (describes distance into linear table */
  99.   /* if the policy is chain */
  100.   int hs_lnum;            /* remember number of lookups */
  101.   int hs_lsum;            /* sum of lookup distances */
  102.   int hs_lavg;            /* average lookup distance */
  103.   /* cumulative for lookup patterns (describes overall efficiency) */
  104.   int hs_clnum;            /* remember number of lookups */
  105.   int hs_clsum;            /* sum of lookup distances */
  106. };
  107.  
  108. /* function declarations */
  109. caddr_t h_new();        /* create new table */
  110. caddr_t h_operation();        /* hash operations */
  111. struct hash_statistics *h_statistics(); /* returns stats on a table */
  112. void h_free();            /* free a table */
  113. /* must specify policy and type */
  114. caddr_t h_redefine();        /* redefine operating parameters for a */
  115.                 /* hash table, forces a rehash */
  116. #define h_rehash(ht,M) (h_redefine((ht),HASH_POLICY_OLD,HASH_TYPE_OLD,\
  117.                    (M),NULL,NULL,NULL,NULL,NULL,NULL))
  118. /* call hash operation for these */
  119. #define h_member(ht,key) (h_operation(HASH_OP_MEMBER,(ht),(key),-1,-1,\
  120.                       NULL,NULL))
  121. #define h_insert(ht,key) (h_operation(HASH_OP_INSERT,(ht),(key),\
  122.                       -1,-1, NULL, NULL))
  123. #define h_delete(ht,key) (h_operation(HASH_OP_DELETE,(ht),(key),-1,-1,\
  124.                        NULL,NULL))
  125.  
  126.  
  127. #endif /* _HASH_HEADER_INCLUDED */
  128.